﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp
{
    /*
     14. 最长公共前缀
    编写一个函数来查找字符串数组中的最长公共前缀。
    如果不存在公共前缀，返回空字符串 ""。
    示例 1:
    输入: ["flower","flow","flight"]
    输出: "fl"
    示例 2:
    输入: ["dog","racecar","car"]
    输出: ""
    解释: 输入不存在公共前缀。
    说明:
    所有输入只包含小写字母 a-z 。   */
    class Action014_最长公共前缀LCP
    {
        public void Test()
        {
            string[] arr1 = {"flower", "flow", "flight"};
            Console.WriteLine("'"+LongestCommonPrefix4(arr1)+ "'" );

            string[] arr2 = {"dog", "racecar", "car"};
            Console.WriteLine("'" + LongestCommonPrefix4(arr2)+ "'");
        }

        #region 1-水平扫描法
        /*利用LCP(S1…Sn)=LCP（...LCP（S1,S2）,S3)...Sn）
         最坏情况：所有字符串均相等，每个字符都参与了比较
         */

        public string LongestCommonPrefix1(string[] strs)
        {
            if (strs.Length == 0)
            {
                return "";
            }

            string prefix = strs[0];
            for (int i = 1; i < strs.Length; i++)
            {
                //如果在新字符串中找不到前缀
                while (strs[i].IndexOf(prefix)!=0)
                {
                    //那么将前缀减少一个尾字符，再试一次
                    prefix = prefix.Substring(0, prefix.Length - 1);
                    if (prefix==string.Empty)
                    {
                        return string.Empty;
                    }
                }
            }

            return prefix;


        }
        #endregion

        #region 2-垂直扫描法
        /*同时比较同一列字符*/
        public string LongestCommonPrefix2(string[] strs)
        {
            if (strs == null || strs.Length == 0)
            {
                return string.Empty;
            }

            for (int i = 0; i < strs[0].Length; i++)
            {
                char c = strs[0][i];
                for (int j = 1; j < strs.Length; j++)
                {
                    if (i == strs[i].Length || c != strs[j][i])
                    {
                        return strs[0].Substring(0, i);
                    }
                }
            }

            return strs[0];
        }
        #endregion

        #region 3-分治法
        /// <summary>
        /// 分治法，利用LCP（S1...Sn） = LCP(LCP(S1...Sk),LCP(Sk+1...Sn))
        /// </summary>
        /// <param name="strs"></param>
        /// <returns></returns>
        public string LongestCommonPrefix3(string[] strs)
        {
            if (strs == null || strs.Length == 0)
            {
                return string.Empty;
            }

            return LongestCommonPrefix3(strs, 0, strs.Length - 1);
        }

        private string LongestCommonPrefix3(string[] strs, int left, int right)
        {
            if (left == right)
            {
                return strs[left];
            }

            int mid = (left + right) / 2;
            string leftPrefix = LongestCommonPrefix3(strs, left, mid);
            string rightPrefix = LongestCommonPrefix3(strs, mid + 1, right);
            return CommonPrefix3(leftPrefix, rightPrefix);
        }

        private string CommonPrefix3(string leftPrefix, string rightPrefix)
        {
            int i = 0;
            //沿着左串比较
            for (i = 0; i < leftPrefix.Length; i++)
            {
                //如果超过了右串长度，或者发现字符不匹配
                if (i == rightPrefix.Length || leftPrefix[i] != rightPrefix[i])
                {
                    return leftPrefix.Substring(0, i);
                }
            }
            //对左串全串匹配
            return leftPrefix;
        }
        #endregion

        #region 4-二分查找

        //1.找到长度最小的串，这是可能的最长前缀
        //2.将该字符串分为两部分 S[1..mid]和S[mid..len]
        //如果前一部分不是公共前缀，则LCP一定不在后一部分中
        //如果前一部分是公共前缀，则LCP一定在后半部分中

        public bool IsCommonPrefix(string[] strs, int len)
        {
            string str0 = strs[0].Substring(0, len);
            foreach (string str in strs)
            {
                if (!str.StartsWith(str0))
                {
                    return false;
                }
            }

            return true;
        }

        public string LongestCommonPrefix4(string[] strs)
        {
            if (strs == null || strs.Length == 0)
            {
                return string.Empty;
            }

            //获取最小长度和对应的字符串
            int minLen = strs[0].Length;
            for (int i = 1; i < strs.Length; i++)
            {
                if (minLen>strs[i].Length)
                {
                    minLen = strs[i].Length;
                }
            }

            int low = 1;
            int high = minLen;
            int mid = 0;
            while (low <= high)
            {
                mid = (low + high) / 2;
                if (IsCommonPrefix(strs, mid))
                {
                    //LCP在后半部分中
                    low = mid+1;
                }
                else
                {
                    //LCP在前半部分中
                    high = mid - 1;
                }
            }

            return strs[0].Substring(0, (low+high)/2);
        }
        #endregion
    }
}
